package features.advance.leetcode.dynamicProgramming.other;

import java.util.Arrays;

/**
 *  动态规划（Dynamic Programming）是一种算法设计技术，它有着相当有趣的历史。
 *  作为一种使多阶段决策过程最优的通用方法，它是在20世纪50年代由一位卓越的美国数学家Richard Bellman所发明的。
 *  因此，这个技术名字中的“programming”是计划和规划的意思，不是代表计算法中的编程。它作为一种重要的工具在
 *  应用数学中的价值被大家认同以后，起码在计算机科学的圈子里，人们不仅用它来解决特定类型的最优问题，
 *  而且最终把它作为一种通用的算法设计技术来使用。在这里，我们正是从这个角度来考虑这种技术的。
 * 　　如果问题是由交叠的子问题所构成的，我们就可以用动态规划技术来解决它。一般来说，
 * 这样的子问题出现在对给定问题求解的递推关系中，这个递推关系中包含了相同类型的更小子问题的解。
 * 动态规划法建议，与其对交叠的子问题一次又一次地求解，还不如对每个较小的子问题只求解一次并把记录记录在表中，
 * 这样就可以从表中得出原始问题的解。
 * 　　——《算法设计与分析基础》
 *
 *  @Description （问题描述）
 *
 * 有一条公路经过Ｖ个村庄，每一个村庄都处在整数的坐标点上（这里假设公路拉直为Ｘ轴）．规划在这条公路上建立Ｐ个邮局，
 * 当然为了方便，这些邮局应建在某Ｐ个村庄上，但是要求让不同村庄的人到邮局要走的总路程最小．
 *
 * @Input
 *
 * 先从键盘读入两个整数Ｖ和Ｐ，然后再读入Ｖ个整数，分别表示Ｖ个村庄的坐标（坐标＞＝０）
 *
 * @Output
 *
 * 输出Ｐ个以空格分隔的整数，按坐标从小到大的顺序给出Ｐ个邮局的坐标．
 *
 * @Sample Input
 *
 *        10 3
 *
 * 1 4 7 19 70 89 105 204 18 40
 *
 * @Sample Output
 *
 * 7 89 204
 *
 * @author LIN
 * @date 2021-04-17
 *
 */
public class Solution01 {


    /**
     *   邮局选址问题
     *
     * (1)动态规划法
     */
    public static int minDistances1(int[] arr, int num) {
            if (arr == null || num < 1 || arr.length < num) {
                return 0;
            }
            int[][] w = new int[arr.length + 1][arr.length + 1];
            // 当一个邮局建在k+1和k的位置的时候，S[k+1] - S[k] = (n - 2k)(arr[k]-arr[k+1])，当k=n/2的时候，S是驻点，
            // 值最低的
            // w[i][j] 从i到j，部署一个邮局的最短距离
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    w[i][j] = w[i][j - 1] + arr[j] - arr[(i + j) / 2];
                }
            }
            // num 邮局数，arr.length村庄个数
            int[][] dp = new int[num][arr.length];//动态规划数组
            for (int j = 0; j != arr.length; j++) {
                dp[0][j] = w[0][j];
            }
            for (int i = 1; i < num; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = 0; k <= j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + w[k + 1][j]);
                    }
                }
            }
            return dp[num - 1][arr.length - 1];
        }
        //(2)优化后的动态规划
        public static int minDistances2(int[] arr, int num) {
            if (arr == null || num < 1 || arr.length < num) {
                return 0;
            }
            int[][] w = new int[arr.length + 1][arr.length + 1];
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    w[i][j] = w[i][j - 1] + arr[j] - arr[(i + j) / 2];
                }
            }
            int[][] dp = new int[num][arr.length];//动态规划数组
            int[][] s = new int[num][arr.length];
            for (int j = 0; j != arr.length; j++) {
                dp[0][j] = w[0][j];
                s[0][j] = 0;
            }
            int minK = 0;
            int maxK = 0;
            int cur = 0;
            for (int i = 1; i < num; i++) {
                for (int j = arr.length - 1; j > i; j--) {
                    minK = s[i - 1][j];
                    maxK = j == arr.length - 1 ? arr.length - 1 : s[i][j + 1];
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = minK; k <= maxK; k++) {
                        cur = dp[i - 1][k] + w[k + 1][j];
                        if (cur <= dp[i][j]) {
                            dp[i][j] = cur;
                            s[i][j] = k;
                        }
                    }
                }
            }
            return dp[num - 1][arr.length - 1];
        }

        // for test
        public static int[] getSortedArray(int len, int range) {
            int[] arr = new int[len];
            for (int i = 0; i != len; i++) {
                arr[i] = (int) (Math.random() * range);
            }
            Arrays.sort(arr);
            return arr;
        }

        // 测试打印数组
        public static void printArray(int[] arr) {
            for (int i = 0; i != arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
        public static void main(String[]args){

            //System.out.println("Hello");
            int[] arr = { -2, -1, 0, 1, 2, 1000 };
            int num = 2;
            arr = new int[]{1, 2, 3, 6, 7, 9, 11, 22, 44, 50};
            num = 5;
            System.out.println(minDistances1(arr, num));
            System.out.println(minDistances2(arr, num));

            int times = 100; // test time
            int len = 1000; // test array length
            int range = 2000; // every number in [0,range)
            int p = 50; // post office number
            long time1 = 0; // method1 all run time
            long time2 = 0;// method2 all run time
            long start = 0;
            long end = 0;
            int res1 = 0;
            int res2 = 0;
            for (int i = 0; i != times; i++) {
                arr = getSortedArray(len, range);
                start = System.currentTimeMillis();
                res1 = minDistances1(arr, p);
                end = System.currentTimeMillis();
                time1 += end - start;
                start = System.currentTimeMillis();
                res2 = minDistances2(arr, p);
                end = System.currentTimeMillis();
                time2 += end - start;
                if (res1 != res2) {
                    printArray(arr);
                    break;
                }
                if (i % 10 == 0) {
                    System.out.print(". ");
                }
            }
            System.out.println();
            System.out.println("method1 all run time(ms): " + time1);
            System.out.println("method2 all run time(ms): " + time2);
        }
}
